function mst = minspanningtree(E)
%MINSPANNINGTREE najde minimalni kostru uplneho grafu
%                E - symetricka NxN matice vah 
%                   ( E(i,j) je delka harny mezi i a j)
%                mst - matice (N-1)x3 hran stromu
%                    radek obsahuje: [i, j, e] - hrana mezi i a j s cenou e
%                (Primuv-Jarnikuv algoritmus)

n = size(E,1);
Out = ones(n,1);     %true/false - oznaceni vrcholu, ktere nejsou v kostre
Out(1) = false;      %na zacatku je v kostre jen prvni vrchol; postupne se bude zvetsovat
D = E(:,1);      %D(i) delka nejkratsi hrany ze stromu do i
D(1) = Inf;
P = ones(n,1);     %hrana delky D(i) vede z P(i)
mst = zeros(n-1,3);  %vystupni matice
for i = 1:(n-1)
    [e, j] = min(D);  %nejelvnejsi hrana, ktera vede ze stromu ven
    mst(i,:) = [P(j), j, e];  %ulozeni do vystupni matice
    Out(j) = false;   %pridani vybraneho vrcholu do stromu
    D(j) = Inf;       %zaruci, ze uz nikdy nebude znovu vybran
    Q = (E(:,j) < D) & Out;  %vrcholy mimo strom, do kterych vede z j kratsi hrana
    Cj = E(:,j);   
    D(Q) = Cj(Q);  
    P(Q) = j;   
end
end

